{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Minimum and Maximum Number of Nodes Between Critical Points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nodesBetweenCriticalPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出临界点之间的最小和最大距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>链表中的 <strong>临界点</strong> 定义为一个 <strong>局部极大值点</strong> <strong>或</strong> <strong>局部极小值点 。</strong></p>\n",
    "\n",
    "<p>如果当前节点的值 <strong>严格大于</strong> 前一个节点和后一个节点，那么这个节点就是一个<strong>&nbsp; 局部极大值点</strong> 。</p>\n",
    "\n",
    "<p>如果当前节点的值 <strong>严格小于</strong> 前一个节点和后一个节点，那么这个节点就是一个<strong>&nbsp; 局部极小值点</strong> 。</p>\n",
    "\n",
    "<p>注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 <strong>局部极大值点 / 极小值点</strong> 。</p>\n",
    "\n",
    "<p>给你一个链表 <code>head</code> ，返回一个长度为 2 的数组<em> </em><code>[minDistance, maxDistance]</code> ，其中<em> </em><code>minDistance</code><em> </em>是任意两个不同临界点之间的最小距离，<code>maxDistance</code> 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 <code>[-1，-1]</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/13/a1.png\" style=\"width: 148px; height: 55px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [3,1]\n",
    "<strong>输出：</strong>[-1,-1]\n",
    "<strong>解释：</strong>链表 [3,1] 中不存在临界点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/13/a2.png\" style=\"width: 624px; height: 46px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [5,3,1,2,5,1,2]\n",
    "<strong>输出：</strong>[1,3]\n",
    "<strong>解释：</strong>存在三个临界点：\n",
    "- [5,3,<em><strong>1</strong></em>,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。\n",
    "- [5,3,1,2,<em><strong>5</strong></em>,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。\n",
    "- [5,3,1,2,5,<em><strong>1</strong></em>,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。\n",
    "第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。\n",
    "第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/14/a5.png\" style=\"width: 624px; height: 39px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,3,2,2,3,2,2,2,7]\n",
    "<strong>输出：</strong>[3,3]\n",
    "<strong>解释：</strong>存在两个临界点：\n",
    "- [1,<em><strong>3</strong></em>,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。\n",
    "- [1,3,2,2,<em><strong>3</strong></em>,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。\n",
    "最小和最大距离都存在于第二个节点和第五个节点之间。\n",
    "因此，minDistance 和 maxDistance 是 5 - 2 = 3 。\n",
    "注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/13/a4.png\" style=\"width: 345px; height: 52px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [2,3,3,2]\n",
    "<strong>输出：</strong>[-1,-1]\n",
    "<strong>解释：</strong>链表 [2,3,3,2] 中不存在临界点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数量在范围 <code>[2, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-minimum-and-maximum-number-of-nodes-between-critical-points](https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-minimum-and-maximum-number-of-nodes-between-critical-points](https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1]', '[5,3,1,2,5,1,2]', '[1,3,2,2,3,2,2,2,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        # if not head or not head.next or not head.next.next:\n",
    "        #     return [-1, -1]\n",
    "        prev_node = head\n",
    "        current = head.next\n",
    "        next_node = current.next\n",
    "        locale_list = []\n",
    "        cnt = 2\n",
    "        while next_node:\n",
    "            if current.val > prev_node.val and current.val > next_node.val:\n",
    "                locale_list.append(cnt)\n",
    "            if current.val < prev_node.val and current.val < next_node.val:\n",
    "                locale_list.append(cnt)\n",
    "            prev_node = prev_node.next\n",
    "            current = current.next\n",
    "            next_node = next_node.next\n",
    "            cnt += 1\n",
    "        if len(locale_list) < 2:\n",
    "            return [-1, -1]\n",
    "        mins = float(\"inf\")\n",
    "        maxs = float(\"-inf\")\n",
    "        for i in range(1, len(locale_list)):\n",
    "            mins = min(mins, locale_list[i] - locale_list[i - 1])\n",
    "        return [mins, locale_list[-1]-locale_list[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "  def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "    p, c = head, head.next\n",
    "    t = 0\n",
    "    st = []\n",
    "    ret = [-1, -1]\n",
    "    while c.next:\n",
    "      n = c.next\n",
    "      if (c.val > p.val and c.val > n.val) or \\\n",
    "        (c.val < p.val and c.val < n.val):\n",
    "        # print(f\"find cri {p.val} {c.val} {n.val}  t {t}\")\n",
    "        if len(st) > 0 and (-1 == ret[0] or ret[0] > t - st[-1]):\n",
    "          ret[0] = t - st[-1]\n",
    "        st.append(t)\n",
    "        \n",
    "      p = c\n",
    "      t += 1\n",
    "      c = n\n",
    "    # print(f\"st {st}\")\n",
    "    if len(st) > 1:\n",
    "      ret[1] = st[-1] - st[0]\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if head is None or head.next is None or head.next.next is None:\n",
    "            return [-1, -1]\n",
    "        i = 1\n",
    "        res = []\n",
    "        pre = head.val\n",
    "        head = head.next\n",
    "        while head.next is not None:\n",
    "            if head.val > pre and head.next is not None and head.val > head.next.val:\n",
    "                res.append(i)\n",
    "            if head.val < pre and head.next is not None and head.val < head.next.val:\n",
    "                res.append(i)\n",
    "            i += 1\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "        if len(res) < 2:\n",
    "            return [-1, -1]\n",
    "        m = res[1]-res[0]\n",
    "        for i in range(2, len(res)):\n",
    "            if res[i]-res[i-1] < m:\n",
    "                m = res[i]-res[i-1]\n",
    "        return [m, res[-1]-res[0]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        res = [10**5, -1]\n",
    "        index = 1\n",
    "        distance = []\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        if not cur:\n",
    "            return [-1, -1]\n",
    "        nxt = cur.next\n",
    "        while nxt:\n",
    "            if (cur.val > pre.val and cur.val > nxt.val) or (cur.val < pre.val and cur.val < nxt.val):\n",
    "                distance.append(index)\n",
    "\n",
    "            if len(distance) > 1:\n",
    "                res[0] = min(res[0], distance[-1] - distance[-2])\n",
    "                res[1] = distance[-1] - distance[0]\n",
    "\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "            nxt = cur.next\n",
    "            index += 1\n",
    "        \n",
    "        if len(distance) <= 1:\n",
    "            return [-1, -1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        A=[]\n",
    "        pre=-1\n",
    "        x=head\n",
    "        p=0\n",
    "        while x:\n",
    "            if x.next and pre!=-1:\n",
    "                if x.val>pre and x.val>x.next.val:\n",
    "                    A.append(p)\n",
    "                elif x.val<pre and x.val<x.next.val:\n",
    "                    A.append(p)\n",
    "            pre=x.val\n",
    "            x=x.next\n",
    "            p+=1\n",
    "        if len(A)<2:\n",
    "            return [-1,-1]\n",
    "        mi=inf\n",
    "        for i in range(len(A)-1):\n",
    "            mi=min(mi,A[i+1]-A[i])\n",
    "        return [mi,A[-1]-A[0]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre = head.val\n",
    "        cur = head.next\n",
    "        if cur.next == None:\n",
    "            return [-1,-1]\n",
    "        ans = []\n",
    "        minnum = 10 ** 5\n",
    "        i = 1\n",
    "        while cur and cur.next:\n",
    "            if pre < cur.val and cur.val > cur.next.val:\n",
    "                ans.append(i)\n",
    "            elif pre > cur.val and cur.val < cur.next.val:\n",
    "                ans.append(i)\n",
    "            if len(ans) >= 2:\n",
    "                minnum = min(minnum,ans[-1] - ans[-2])\n",
    "            pre = cur.val\n",
    "            cur = cur.next\n",
    "            i += 1\n",
    "        if len(ans) < 2:\n",
    "            return [-1,-1]\n",
    "        return [minnum,ans[-1] - ans[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre = min_dist = inf\n",
    "        idx_list = []\n",
    "        pos = 0\n",
    "        p = head \n",
    "        while p and p.next:\n",
    "            if p.next and pre != inf and (pre < p.val > p.next.val or pre > p.val < p.next.val):\n",
    "                if idx_list:\n",
    "                    min_dist = min(min_dist, pos-idx_list[-1])\n",
    "                idx_list.append(pos)\n",
    "            pre = p.val \n",
    "            p = p.next\n",
    "            pos += 1\n",
    "        if len(idx_list) < 2:\n",
    "            return [-1, -1]\n",
    "        return [min_dist, idx_list[-1]-idx_list[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        arr = []\n",
    "        i = 1\n",
    "        while head and head.next and head.next.next:\n",
    "            if head.next.val > head.val  and head.next.val > head.next.next.val:\n",
    "                arr.append(i)\n",
    "            elif head.next.val < head.val and head.next.val < head.next.next.val:\n",
    "                arr.append(i)\n",
    "            head = head.next\n",
    "            i += 1\n",
    "        \n",
    "        if len(arr) < 2:\n",
    "            return [-1, -1]\n",
    "        \n",
    "        maxnum = arr[-1] - arr[0]\n",
    "        minnum = i\n",
    "\n",
    "        for j in range(1, len(arr)):\n",
    "            minnum = min(minnum, arr[j] - arr[j-1])\n",
    "\n",
    "        return [minnum, maxnum]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head or not head.next or not head.next.next:\n",
    "            return [-1, -1]\n",
    "        prev_node = head\n",
    "        current = head.next\n",
    "        next_node = current.next\n",
    "        locale_list = []\n",
    "        cnt = 2\n",
    "        while next_node:\n",
    "            if current.val > prev_node.val and current.val > next_node.val:\n",
    "                locale_list.append(cnt)\n",
    "            if current.val < prev_node.val and current.val < next_node.val:\n",
    "                locale_list.append(cnt)\n",
    "            prev_node = prev_node.next\n",
    "            current = current.next\n",
    "            next_node = next_node.next\n",
    "            cnt += 1\n",
    "        if len(locale_list) < 2:\n",
    "            return [-1, -1]\n",
    "        mins = float(\"inf\")\n",
    "        maxs = float(\"-inf\")\n",
    "        for i in range(1, len(locale_list)):\n",
    "            mins = min(mins, locale_list[i] - locale_list[i - 1])\n",
    "        return [mins, locale_list[-1]-locale_list[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        tmp = []\n",
    "        i = 2\n",
    "        pre = head\n",
    "        p = head.next\n",
    "        while p:\n",
    "            if p.next and p.val > pre.val and p.val > p.next.val:\n",
    "                tmp.append(i)\n",
    "            if p.next and p.val < pre.val and p.val < p.next.val:\n",
    "                tmp.append(i)\n",
    "            i += 1\n",
    "            pre = p\n",
    "            p = p.next\n",
    "        if len(tmp) < 2:\n",
    "            return [-1,-1]\n",
    "        min_ = 100000\n",
    "        for i in range(len(tmp)-1):\n",
    "            min_ = min(min_,tmp[i+1]-tmp[i])\n",
    "        return [min_,tmp[-1]-tmp[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        first, second = head, head.next\n",
    "        nums = []\n",
    "        i = 1\n",
    "        while second.next:\n",
    "            if second.val > first.val and second.val > second.next.val:\n",
    "                nums.append(i)\n",
    "            elif second.val < first.val and second.val < second.next.val:\n",
    "                nums.append(i)\n",
    "            first = second\n",
    "            second = second.next\n",
    "            i += 1\n",
    "        if len(nums) < 2:\n",
    "            return [-1, -1]\n",
    "        minVal = inf\n",
    "        for i in range(len(nums) - 1):\n",
    "            minVal = min(minVal, nums[i + 1] - nums[i])\n",
    "        return [minVal, nums[-1] - nums[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pos = []\n",
    "        idx , pre = 0 , 0 \n",
    "        while head != None :\n",
    "            if idx != 0 and head.next != None :\n",
    "                if head.val > pre and head.val > head.next.val or head.val < pre and head.val < head.next.val :\n",
    "                    pos.append(idx) \n",
    "            pre = head.val\n",
    "            idx += 1 \n",
    "            head = head.next\n",
    "        if len(pos) < 2 :\n",
    "            return [-1,-1]\n",
    "        min_ = 0x3f3f3f3f \n",
    "        for i, j in pairwise(pos):\n",
    "            min_ = min(min_  , j-i) \n",
    "        return [min_,pos[-1]-pos[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pos=[]\n",
    "        min_num,max_num=float(\"inf\"),-1\n",
    "        p,q=-1,-1\n",
    "        start=-1\n",
    "        index=1\n",
    "        pre=head\n",
    "        now=head.next\n",
    "        while now:\n",
    "            if now.next:\n",
    "                if pre.val>now.val and now.next.val>now.val:\n",
    "                    pos.append(index)\n",
    "                    if start==-1:\n",
    "                        start=index\n",
    "                        p=index\n",
    "                    else:\n",
    "                        min_num,max_num=min(min_num,index-p),index-start\n",
    "                        p=index\n",
    "                elif pre.val<now.val and now.next.val<now.val:\n",
    "                    pos.append(index)\n",
    "                    if start==-1:\n",
    "                        start=index\n",
    "                        p=index\n",
    "                    else:\n",
    "                        min_num,max_num=min(min_num,index-p),index-start\n",
    "                        p=index\n",
    "            pre,now=pre.next,now.next\n",
    "            index+=1\n",
    "        return [min_num if max_num!=-1 else -1,max_num]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ls = []\n",
    "        while head:\n",
    "            ls.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        pre = -1\n",
    "\n",
    "        min_ = float('inf')\n",
    "        max_ = float('-inf')\n",
    "        first = -1\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(1, len(ls) - 1):\n",
    "            if (ls[i - 1] < ls[i] and ls[i] > ls[i + 1]) or (ls[i - 1] > ls[i] and ls[i] < ls[i + 1]):\n",
    "                if pre != -1:\n",
    "                    min_ = min(min_, i - pre)\n",
    "                \n",
    "                if pre == -1:\n",
    "                    first = i\n",
    "                \n",
    "                pre = i \n",
    "                cnt += 1\n",
    "        \n",
    "        max_ = pre - first\n",
    "\n",
    "        if cnt < 2:\n",
    "            return [-1, -1]\n",
    "        else:\n",
    "            return [min_, max_]\n",
    "        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                print(i,head.val)\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        maxpos = -1\n",
    "        minpos = -1\n",
    "        prepos = -1\n",
    "        pre = head\n",
    "        now = head.next\n",
    "        ret = 1 << 31\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            nxt = now.next\n",
    "            if not nxt:\n",
    "                break\n",
    "            cnt += 1\n",
    "            if not nxt:\n",
    "                return ma - mi if mi != 1 << 30 else [-1, -1]\n",
    "            if (now.val > nxt.val and now.val > pre.val) or (now.val < nxt.val and now.val < pre.val):\n",
    "                if minpos == -1:\n",
    "                    minpos = cnt\n",
    "                else:\n",
    "                    ret = min(ret, cnt - prepos)\n",
    "                # print(prepos, cnt,  pre.val, now.val, nxt.val)\n",
    "                prepos = maxpos = cnt\n",
    "            pre, now = now, nxt\n",
    "        if ret == 1 << 31:\n",
    "            return [-1, -1]\n",
    "        return [ret, maxpos - minpos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head or not head.next:\n",
    "            return([-1,-1])\n",
    "        \n",
    "        min_res,max_res = float('inf'),float('-inf')\n",
    "        early,late = None,None\n",
    "        \n",
    "        pre = head\n",
    "        cur = pre.next\n",
    "        i = 1\n",
    "        while cur and cur.next:\n",
    "            if ((cur.val < pre.val) and (cur.val < cur.next.val)) or \\\n",
    "               ((cur.val > pre.val) and (cur.val > cur.next.val)):\n",
    "                    if early is None:\n",
    "                        early = i\n",
    "                    else:\n",
    "                        if late is None:\n",
    "                            late = i\n",
    "                            min_res = (late - early)\n",
    "                        else:\n",
    "                            min_res = min([min_res, (i - late)])\n",
    "                            late = i\n",
    "                    \n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "            i += 1\n",
    "        \n",
    "        if early and late:\n",
    "            max_res = late - early\n",
    "        print(min_res,max_res,early,late)\n",
    "        \n",
    "        if late:\n",
    "            return([min_res,max_res])\n",
    "        else:\n",
    "            return([-1,-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if head is None:\n",
    "            return [-1, -1]\n",
    "\n",
    "        firstlocal = -1\n",
    "        lastlocal = -1\n",
    "        mindist = float('inf')\n",
    "\n",
    "        prevv = head.val\n",
    "        i = 1\n",
    "        head = head.next\n",
    "        while head and head.next:\n",
    "            if (head.val > prevv and head.val > head.next.val) or (head.val < prevv and head.val < head.next.val):\n",
    "                if lastlocal == -1:\n",
    "                    firstlocal = lastlocal = i\n",
    "                else:\n",
    "                    mindist = min(mindist, i - lastlocal)\n",
    "                    lastlocal = i\n",
    "            i += 1\n",
    "            prevv = head.val\n",
    "            head = head.next\n",
    "\n",
    "        if mindist == float('inf'):\n",
    "            return [-1,-1]\n",
    "        return [mindist, lastlocal - firstlocal]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre_val = head.val\n",
    "        start = None\n",
    "        end = None\n",
    "        min_dis = float(\"inf\")\n",
    "        count = 0\n",
    "        while head and head.next:\n",
    "            \n",
    "            if (head.val > pre_val and head.val > head.next.val) or (head.val < pre_val and head.val < head.next.val):\n",
    "                if start is None:\n",
    "                    start = count\n",
    "                if end:\n",
    "                    min_dis = min(min_dis, count - end)\n",
    "                end = count\n",
    "            pre_val = head.val\n",
    "            count += 1\n",
    "            head = head.next\n",
    "        if start == end:\n",
    "            return[-1, -1]\n",
    "        return [min_dis, end-start]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        curr = head.next.next\n",
    "        last1 = head.next\n",
    "        last2 = head\n",
    "        if not curr: return [-1, -1]\n",
    "\n",
    "        index = 0\n",
    "        arr = []\n",
    "        mi = float('inf')\n",
    "        while curr:\n",
    "            if last2.val < last1.val > curr.val or last2.val > last1.val < curr.val:\n",
    "                if not arr:\n",
    "                    arr.append(index)\n",
    "                else:\n",
    "                    mi = min(mi, index - arr[-1])\n",
    "                    arr.append(index)\n",
    "            index += 1\n",
    "            curr = curr.next\n",
    "            last1 = last1.next\n",
    "            last2 = last2.next\n",
    "\n",
    "        if len(arr) in (0, 1): return[-1, -1]\n",
    "        return [mi, arr[-1] - arr[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                print(i,head.val)\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        min_left = -1\n",
    "        cur_left = -1\n",
    "        cur_right = -1\n",
    "        cur_num = 1\n",
    "        max_len = 0\n",
    "        min_len = 10000000000\n",
    "        while cur.next:\n",
    "            print(cur_num)\n",
    "            if (pre.val > cur.val and cur.val <cur.next.val) or (pre.val < cur.val and cur.val >cur.next.val):\n",
    "                \n",
    "                if min_left == -1:\n",
    "                    min_left = cur_num\n",
    "                if cur_left == -1:\n",
    "                    cur_left = cur_num\n",
    "                elif cur_left!=-1 and cur_right==-1:\n",
    "                    cur_right = cur_num\n",
    "                elif cur_left!=-1 and cur_right!=-1:\n",
    "                    cur_right = cur_num\n",
    "\n",
    "                if cur_right>cur_left:\n",
    "                    max_len = cur_right - min_left\n",
    "                    min_len = min(min_len,cur_right-cur_left)\n",
    "                    cur_left = cur_right\n",
    "            cur_num+=1\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "            \n",
    "        if cur_right == -1:\n",
    "            return [-1,-1]\n",
    "        else:\n",
    "            return [min_len,max_len]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        ans = [float('inf'),-float('inf')]\n",
    "        mv1,mv2 = -1,-1\n",
    "        p = head\n",
    "        v = []\n",
    "        while p:\n",
    "            v.append(p.val)\n",
    "            p = p.next\n",
    "        for i in range(1,len(v) - 1):\n",
    "            if v[i] > v[i - 1] and v[i] > v[i + 1]:\n",
    "                if mv1 != -1:\n",
    "                    ans[0] = min(ans[0],i - mv1)\n",
    "                if mv2 != -1:\n",
    "                    ans[1] = max(ans[1],i - mv2)\n",
    "                if mv2 == -1:\n",
    "                    mv2 = i\n",
    "                mv1 = i\n",
    "            if v[i] < v[i - 1] and v[i] < v[i + 1]:\n",
    "                if mv1 != -1:\n",
    "                    ans[0] = min(ans[0],i - mv1)\n",
    "                if mv2 != -1:\n",
    "                    ans[1] = max(ans[1],i - mv2)\n",
    "                if mv2 == -1:\n",
    "                    mv2 = i\n",
    "                mv1 = i\n",
    "        if ans[0] == float('inf'):\n",
    "            ans[0] = -1\n",
    "        if ans[1] == -float('inf'):\n",
    "            ans[1] = -1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                print(i,head.val)\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        minDistance = maxDistance = -1\n",
    "        first, j, i = None, None, 1\n",
    "        pre, cur, last = head, head.next, head.next.next\n",
    "        while last:\n",
    "            if (pre.val < cur.val and cur.val > last.val) or (pre.val > cur.val and cur.val < last.val):\n",
    "                if first is None:\n",
    "                    first = i\n",
    "                else:\n",
    "                    if j is None:\n",
    "                        maxDistance = minDistance = i-first\n",
    "                    else:\n",
    "                        maxDistance = i-first\n",
    "                        minDistance = min(minDistance, i-j)\n",
    "                    j = i\n",
    "\n",
    "            pre, cur, last, i = cur, last, last.next, i+1\n",
    "        return [minDistance, maxDistance]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                print(i,head.val)\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        first_node = None   # 用于储存第一个临界点的深度\n",
    "        last_node = -inf    # 用于储存最后一个临界点的深度\n",
    "        small = inf         # 最小间距\n",
    "        depth = 0           # 深度\n",
    "\n",
    "        while head.next.next:\n",
    "            f_value = head.val  # 父节点的值\n",
    "            head = head.next    # 步进\n",
    "            depth += 1\n",
    "            if f_value < head.val > head.next.val or f_value > head.val < head.next.val:\n",
    "                if not first_node:\n",
    "                    first_node = depth\n",
    "                small = min(small, depth - last_node)\n",
    "                last_node = depth\n",
    "            \n",
    "\n",
    "        # 如果小于2个临界点，返回[-1, -1]\n",
    "        if not first_node or first_node == last_node:\n",
    "            return [-1, -1]\n",
    "        return [small, last_node - first_node]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        first = None\n",
    "        last = None\n",
    "        i = 1\n",
    "        ans = 0\n",
    "        min_d, max_d = -1, -1\n",
    "        while head and head.next and head.next.next:\n",
    "            #print('first:%s, i:%d, last:%s' % (str(first), i, str(last)))\n",
    "            pre, cur, next = head.val, head.next.val, head.next.next.val\n",
    "            #print('(%d,%d,%d)' % (pre, cur, next))\n",
    "            if cur > max(pre, next) or cur < min(pre, next):\n",
    "                if first:\n",
    "                    if min_d == -1:\n",
    "                        min_d = i - last\n",
    "                    else:\n",
    "                        min_d = min(min_d, i - last)\n",
    "                    max_d = i - first\n",
    "                else:\n",
    "                    first = i\n",
    "                last = i\n",
    "                \n",
    "\n",
    "            i += 1\n",
    "            head = head.next\n",
    "        return min_d, max_d\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head.next:\n",
    "            return [-1, -1]\n",
    "\n",
    "        first_node = None   # 用于储存第一个临界点的深度\n",
    "        last_node = -inf     # 用于储存最后一个临界点的深度\n",
    "        f_value = head.val  # 父节点的值\n",
    "        head = head.next    # 当前结点\n",
    "        depth = 1           # 深度\n",
    "        small = inf         # 最小间距\n",
    "        while head.next:\n",
    "            if f_value < head.val > head.next.val or f_value > head.val < head.next.val:\n",
    "                if not first_node:\n",
    "                    first_node = depth\n",
    "                small = min(small, depth - last_node)\n",
    "                last_node = depth\n",
    "\n",
    "            f_value = head.val\n",
    "            head = head.next\n",
    "            depth += 1\n",
    "\n",
    "        if not first_node or first_node == last_node:\n",
    "            return [-1, -1]\n",
    "        return [small, last_node - first_node]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        mindis = math.inf\n",
    "        pos = []\n",
    "        i=2\n",
    "        pre_pose=0\n",
    "        while head and head.next.next:\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "            back = head.next.val\n",
    "            if (pre<head.val and head.val>back) or (head.val<pre and head.val<back):\n",
    "                print(i,head.val)\n",
    "                pos.append(i)\n",
    "                if pre_pose!=0:\n",
    "                    mindis = min(mindis,i-pre_pose)\n",
    "                pre_pose=i\n",
    "            i+=1\n",
    "        return [mindis,pos[-1]-pos[0]] if len(pos)>=2 else [-1,-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        a, b = head.val, head.next.val\n",
    "        head = head.next\n",
    "        x = y = 0\n",
    "        while head.next:\n",
    "            c = head.next.val\n",
    "            if a < b > c or a > b < c:\n",
    "                x = 1\n",
    "                a, b = b, c\n",
    "                head = head.next\n",
    "                break\n",
    "            a, b = b, c\n",
    "            head = head.next\n",
    "        fhx = float('inf')\n",
    "        fhd = 0\n",
    "        while head.next:\n",
    "            c = head.next.val\n",
    "            if a < b > c or a > b < c:\n",
    "                fhx = min(fhx, x-y)\n",
    "                fhd = x\n",
    "                y = x\n",
    "            x += 1\n",
    "            a, b = b, c\n",
    "            head = head.next\n",
    "        if y == 0:\n",
    "            return [-1,-1]\n",
    "        return [fhx, fhd]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head or not head.next or not head.next.next:\n",
    "            return [-1, -1]\n",
    "            \n",
    "        h = head\n",
    "        m = head.next\n",
    "        t = head.next.next\n",
    "\n",
    "        min_ = float('inf')\n",
    "        max_ = float('-inf')\n",
    "        pre = -1\n",
    "        first = -1\n",
    "        idx = 0\n",
    "        cnt = 0\n",
    "        while h and m and t:\n",
    "            if (m.val > h.val and m.val > t.val) or (m.val < h.val and m.val < t.val):\n",
    "                if pre == -1:\n",
    "                    pre = idx\n",
    "                    first = idx\n",
    "                else:\n",
    "                    min_ = min(min_, idx - pre)\n",
    "                    pre = idx\n",
    "            \n",
    "                cnt += 1\n",
    "\n",
    "            idx += 1\n",
    "            h = h.next\n",
    "            m = m.next\n",
    "            t = t.next\n",
    "        \n",
    "        max_ = pre - first\n",
    "        \n",
    "        if cnt < 2:\n",
    "            return [-1, -1]\n",
    "        else:\n",
    "            return [min_, max_]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre = head\n",
    "        head = head.next\n",
    "        cur = first = -1\n",
    "        mind = 1 << 20\n",
    "        maxd = -1\n",
    "        i = 0\n",
    "        while head and head.next:\n",
    "            if (head.val < pre.val and head.val < head.next.val) or (head.val > pre.val and head.val > head.next.val):\n",
    "                if first == -1:\n",
    "                    first = cur = i\n",
    "                else:\n",
    "                    if i - cur < mind:\n",
    "                        mind = i - cur\n",
    "                    maxd = i - first\n",
    "                    cur = i\n",
    "            i += 1\n",
    "            pre = head\n",
    "            head = head.next\n",
    "                \n",
    "        if first == -1 or maxd == -1:\n",
    "            return [-1, -1]\n",
    "        return [mind, maxd] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        minDist = maxDist = -1\n",
    "        first = last = -1\n",
    "        pos = 0\n",
    "\n",
    "        cur = head\n",
    "        while cur.next.next:\n",
    "            x, y, z = cur.val, cur.next.val, cur.next.next.val\n",
    "            if y > max(x, z) or y < min(x, z):\n",
    "                if last != -1:\n",
    "                    minDist = (pos - last if minDist == -1 else min(minDist, pos - last))\n",
    "                    maxDist = max(maxDist, pos - first)\n",
    "                if first == -1:\n",
    "                    first = pos\n",
    "                last = pos\n",
    "            cur = cur.next\n",
    "            pos += 1\n",
    "        return [minDist, maxDist]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        res = [-1, -1]\n",
    "        curr = 0\n",
    "        last = -1\n",
    "        while head.next and head.next.next:\n",
    "            flag = (head.next.val - head.val) * (head.next.next.val - head.next.val)\n",
    "            head = head.next\n",
    "            curr += 1\n",
    "            if flag < 0:\n",
    "                if last != -1:\n",
    "                    if res[0] == -1 or curr - last < res[0]:\n",
    "                        res[0] = curr - last\n",
    "                    if res[1] == -1:\n",
    "                        res[1] = 0\n",
    "                    res[1] += curr - last\n",
    "                last = curr\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        minDist=maxDist = -1\n",
    "        first = last = -1\n",
    "        pos = 0\n",
    "        cur = head\n",
    "        while cur.next.next:\n",
    "            x, y, z = cur.val, cur.next.val, cur.next.next.val\n",
    "            if y > max(x, z) or y< min(x, z):\n",
    "                if last != -1:\n",
    "                    minDist = (pos - last if minDist == -1 else min(minDist, pos - last))\n",
    "                    maxDist = max(maxDist, pos - first)\n",
    "                if first == -1:\n",
    "                    first = pos\n",
    "                last = pos\n",
    "            cur = cur.next\n",
    "            pos += 1\n",
    "        return [minDist , maxDist]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        a, b = head.val, head.next.val\n",
    "        head = head.next\n",
    "        x = y = 0\n",
    "        while head.next:\n",
    "            c = head.next.val\n",
    "            if a < b > c or a > b < c:\n",
    "                x = 1\n",
    "                a, b = b, c\n",
    "                head = head.next\n",
    "                break\n",
    "            a, b = b, c\n",
    "            head = head.next\n",
    "        fhx = float('inf')\n",
    "        fhd = 0\n",
    "        while head.next:\n",
    "            c = head.next.val\n",
    "            if a < b > c or a > b < c:\n",
    "                fhx = min(fhx, x-y)\n",
    "                fhd = x\n",
    "                y = x\n",
    "            x += 1\n",
    "            a, b = b, c\n",
    "            head = head.next\n",
    "        if y == 0:\n",
    "            return [-1,-1]\n",
    "        return [fhx, fhd]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        nums = []\n",
    "        p = head\n",
    "        while p:\n",
    "            nums.append(p.val)\n",
    "            p = p.next\n",
    "\n",
    "        arr = []\n",
    "        lenA = len(nums)\n",
    "        for i in range(1, lenA - 1):\n",
    "            if nums[i - 1] > nums[i]  < nums[i + 1]:\n",
    "                arr.append(i)\n",
    "            elif nums[i-1] < nums[i] > nums[i+1]:\n",
    "                arr.append(i)\n",
    "        \n",
    "        if len(arr) < 2:\n",
    "            return [-1,-1]\n",
    "\n",
    "        max_idx = arr[-1] - arr[0]\n",
    "        min_idx = float('inf')\n",
    "        for i in range(1,len(arr)):\n",
    "            min_idx = min(min_idx, arr[i] - arr[i-1])\n",
    "        return [min_idx,max_idx]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head or not head.next:\n",
    "            return [-1, -1]\n",
    "        ans = [inf, -inf]\n",
    "        preVal, preIdx, beginIdx, i = head.val, -1, -1, 1\n",
    "        cur = head.next\n",
    "        while cur and cur.next:\n",
    "            if cur.val > preVal and cur.val > cur.next.val or cur.val < preVal and cur.val < cur.next.val:\n",
    "                if preIdx != -1:\n",
    "                    ans[0] = min(ans[0], i - preIdx)\n",
    "                if beginIdx != -1:\n",
    "                    ans[1] = max(ans[1], i - beginIdx)\n",
    "                else:\n",
    "                    beginIdx = i\n",
    "                preIdx = i\n",
    "            i += 1\n",
    "            preVal = cur.val\n",
    "            cur = cur.next\n",
    "        if ans == [inf, -inf]:\n",
    "            return [-1, -1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        '''\n",
    "        use pre to track previous node, cur to tarck current node\n",
    "        use cnt to store the current nodes number\n",
    "\n",
    "        when pre.val <(>) cur.val and cur.next.val <(>) cur.val, this node is criticality\n",
    "        use loc to store the prevous criticality\n",
    "        max_length to store the max_distance, and min_length = store the min_Distance\n",
    "        upgrade max_length = max(max_length, cnt-loc), min_length = min(min_length, cnt-loc)\n",
    "        '''\n",
    "\n",
    "        max_length = -1\n",
    "        min_length = -1\n",
    "\n",
    "        cnt = 1\n",
    "        loc = -1\n",
    "        first_loc = -1\n",
    "\n",
    "        cur = head.next\n",
    "        pre = head\n",
    "\n",
    "        while cur:\n",
    "            cnt += 1\n",
    "\n",
    "            if cur.next and ((cur.val>pre.val and cur.val>cur.next.val) or (cur.val<pre.val and cur.val<cur.next.val)):\n",
    "                if loc == -1: \n",
    "                    loc = cnt\n",
    "                    first_loc = cnt\n",
    "                \n",
    "                else:\n",
    "                    if min_length == -1: min_length = pow(10,5)\n",
    "\n",
    "                    min_length = min(min_length, cnt-loc)\n",
    "                    max_length = max(max_length, cnt-first_loc)\n",
    "\n",
    "                    loc = cnt\n",
    "            \n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "        \n",
    "        return [min_length, max_length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        min_left = -1\n",
    "        cur_left = -1\n",
    "        cur_right = -1\n",
    "        cur_num = 1\n",
    "        max_len = 0\n",
    "        min_len = 10000000000\n",
    "        while cur.next:\n",
    "\n",
    "            if (pre.val > cur.val and cur.val <cur.next.val) or (pre.val < cur.val and cur.val >cur.next.val):\n",
    "                \n",
    "                if min_left == -1:\n",
    "                    min_left = cur_num\n",
    "                if cur_left == -1:\n",
    "                    cur_left = cur_num\n",
    "                elif cur_left!=-1 and cur_right==-1:\n",
    "                    cur_right = cur_num\n",
    "                elif cur_left!=-1 and cur_right!=-1:\n",
    "                    cur_right = cur_num\n",
    "\n",
    "                if cur_right>cur_left:\n",
    "                    max_len = cur_right - min_left\n",
    "                    min_len = min(min_len,cur_right-cur_left)\n",
    "                    cur_left = cur_right\n",
    "            cur_num+=1\n",
    "            pre = cur\n",
    "            cur = cur.next\n",
    "            \n",
    "        if cur_right == -1:\n",
    "            return [-1,-1]\n",
    "        else:\n",
    "            return [min_len,max_len]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre = head.val\n",
    "        head = head.next\n",
    "        ans = [-1, -1]\n",
    "        preLoc = fstLoc = None\n",
    "        index = 1\n",
    "        while head and head.next:\n",
    "            if (head.val - pre) * (head.val - head.next.val) > 0:\n",
    "                if not preLoc:\n",
    "                    fstLoc = index\n",
    "                elif ans == [-1, -1]:\n",
    "                    ans = [index - preLoc] * 2\n",
    "                else:\n",
    "                    ans = [min(ans[0], index - preLoc), index - fstLoc]\n",
    "                preLoc = index\n",
    "            index += 1\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head or not head.next or not head.next.next:\n",
    "            return [-1,-1]\n",
    "        n=1\n",
    "        list1=[]\n",
    "        ans=[]\n",
    "        while head.next.next:\n",
    "            if head.val<head.next.val>head.next.next.val:\n",
    "                list1.append(n+1)\n",
    "            if head.val>head.next.val<head.next.next.val:\n",
    "                list1.append(n+1)\n",
    "            n+=1\n",
    "            head=head.next\n",
    "        if len(list1)<2:\n",
    "            return [-1,-1]\n",
    "        difference = [list1[i] - list1[i-1] for i in range(1, len(list1))]\n",
    "        Min=min(difference)\n",
    "        ans.append(Min)\n",
    "        ans.append(list1[-1] - list1[0])\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        lst = []\n",
    "        while head:\n",
    "            lst.append(head.val)\n",
    "            head = head.next\n",
    "        n = len(lst)\n",
    "        ind = []\n",
    "        for i in range(1, n-1):\n",
    "            x1, x, x2 = lst[i-1], lst[i], lst[i+1]\n",
    "            if x < x1 and x < x2:\n",
    "                ind.append(i)\n",
    "            elif x > x1 and x > x2:\n",
    "                ind.append(i)\n",
    "        if len(ind) < 2:\n",
    "            return [-1, -1]\n",
    "        low = min(ind[i+1]-ind[i] for i in range(len(ind)-1))\n",
    "        high = ind[-1] - ind[0]\n",
    "        return [low, high]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        pre = head.val\n",
    "        head = head.next\n",
    "        ans = [-1, -1]\n",
    "        preLoc = fstLoc = None\n",
    "        index = 1\n",
    "        while head and head.next:\n",
    "            if (head.val - pre) * (head.val - head.next.val) > 0:\n",
    "                if not preLoc:\n",
    "                    fstLoc = index\n",
    "                elif ans == [-1, -1]:\n",
    "                    ans = [index - preLoc] * 2\n",
    "                else:\n",
    "                    ans = [min(ans[0], index - preLoc), index - fstLoc]\n",
    "                preLoc = index\n",
    "            index += 1\n",
    "            pre = head.val\n",
    "            head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        minDist = maxDist = -1\n",
    "        first = last = -1\n",
    "        pos = 0\n",
    "\n",
    "        cur = head\n",
    "        while cur.next.next:\n",
    "            x, y, z = cur.val, cur.next.val, cur.next.next.val\n",
    "\n",
    "            if y > max(x,z) or y < min(x,z):\n",
    "                if last != -1:\n",
    "\n",
    "                    minDist = (pos - last if minDist == -1 else min(minDist, pos - last))\n",
    "\n",
    "                    maxDist = pos - first\n",
    "\n",
    "                if first == -1:\n",
    "                    first = pos\n",
    "                \n",
    "                last = pos\n",
    "\n",
    "            cur = cur.next\n",
    "            pos += 1\n",
    "\n",
    "        return [minDist, maxDist] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        if not head or not head.next or not head.next.next:\n",
    "            return [-1, -1]\n",
    "        prev_node = head\n",
    "        current = head.next\n",
    "        next_node = current.next\n",
    "        locale_list = []\n",
    "        cnt = 2\n",
    "        while next_node:\n",
    "            print(current.val)\n",
    "            if current.val > prev_node.val and current.val > next_node.val:\n",
    "                locale_list.append(cnt)\n",
    "            if current.val < prev_node.val and current.val < next_node.val:\n",
    "                locale_list.append(cnt)\n",
    "            prev_node = prev_node.next\n",
    "            current = current.next\n",
    "            next_node = next_node.next\n",
    "            cnt += 1\n",
    "        print(locale_list)\n",
    "        if len(locale_list) < 2:\n",
    "            return [-1, -1]\n",
    "        mins = float(\"inf\")\n",
    "        maxs = float(\"-inf\")\n",
    "        for i in range(1, len(locale_list)):\n",
    "            mins = min(mins, locale_list[i] - locale_list[i - 1])\n",
    "        return [mins, locale_list[-1]-locale_list[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:\n",
    "        def scan(head, arr):\n",
    "            if not head:\n",
    "                return\n",
    "            cursor = head\n",
    "            while cursor:\n",
    "                arr.append(cursor.val)\n",
    "                cursor = cursor.next\n",
    "        arr = []\n",
    "        scan(head, arr)\n",
    "        # 检查并校验 极值点\n",
    "        # print(\"arr=\", arr[1:-1])\n",
    "        if arr.__len__() <= 2:\n",
    "            return [-1, -1]\n",
    "        indexs = []\n",
    "        for i in range(1, arr.__len__()-1):\n",
    "            if arr[i] < arr[i-1] and arr[i] < arr[i+1]:\n",
    "                indexs.append(i)\n",
    "                continue\n",
    "            if arr[i] > arr[i-1] and arr[i] > arr[i+1]:\n",
    "                indexs.append(i)\n",
    "                continue\n",
    "        if indexs.__len__() <= 1:\n",
    "            return [-1, -1]\n",
    "        elif indexs.__len__() == 2:\n",
    "            return [abs(indexs[0]-indexs[1]), abs(indexs[0]-indexs[1])]\n",
    "        # 分别求最小距离和最大距离\n",
    "        ans = [-1, abs(indexs[-1]-indexs[0])]\n",
    "        # print(\"indexs=\", indexs)\n",
    "        minimum = 10**6\n",
    "        for i in range(1, indexs.__len__()):\n",
    "            minimum = min(minimum, abs(indexs[i]-indexs[i-1]))\n",
    "        ans[0] = minimum\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
